/*
 * @lc app=leetcode.cn id=993 lang=cpp
 *
 * [993] 二叉树的堂兄弟节点
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <bits/stdc++.h>
using namespace std;
struct TreeNode;
class Solution
{
public:
    bool isCousins(TreeNode *root, int x, int y)
    {
        queue<pair<TreeNode *, TreeNode *>> q[2];
        q[0].push(make_pair(root, (TreeNode *)NULL));
        int flag = 0;
        while (!q[0].empty() || !q[1].empty())
        {
            bool x_find = false, y_find = false;
            TreeNode* fx = NULL, *fy = NULL;
            while (!q[flag].empty())
            {
                auto it = q[flag].front();
                auto n = it.first;

                q[flag].pop();

                if (x == n->val)
                {
                    x_find = true;
                    fx = it.second;
                }
                if (y == n->val)
                {
                    y_find = true;
                    fy = it.second;
                }

                if (n->left)
                {
                    q[1 - flag].push(make_pair(n->left, n));
                }
                if (n->right)
                {
                    q[1 - flag].push(make_pair(n->right, n));
                }
            }
            if (x_find && y_find && fx != fy)
                return true;
            if (x_find || y_find)
                return false;
            flag = 1 - flag;
        }

        return false;
    }
};
// @lc code=end
